One use of the Internet is to allow users to access remotely stored content, such as documents and multimedia. To do so, typically a person operates a client device to access content on a remote origin server over the Internet. The client device may be, for example, a personal computer (PC) or a hand-held device such as a personal digital assistant (PDA) or cellular telephone. The client normally includes a software application known as a browser, which can provide this functionality. A person using the client typically operates the browser to locate and select content stored on the origin server, such as a web page or a multimedia file. In response to this user input, the browser sends a request for the content over the Internet to the origin server on which the content resides. In response, the origin server returns a response containing the requested content to the client, which outputs the content in the appropriate manner (e.g., it displays the web page or plays the audio file). The request and response may be communicated using well-known protocols, such as transmission control protocol/Internet protocol (TCP/IP) and hypertext transfer protocol (HTTP).
It is often desirable to cache network content in a device on the network that is located logically between the clients and the origin servers. The main purpose of caching content in this way is to reduce the latency associated with servicing content requests from clients. Storing certain content locally in the cache avoids the necessity of having to forward every content request over the network to the corresponding origin server and having to wait for a response. Instead, if the cache receives a request for content which it has cached, it simply provides the requested content to the requesting client (subject to any required authentication and/or authorization) without involving the origin server. An example of a device which has this functionality is the NetCache product designed and manufactured by Network Appliance, Inc. of Sunnyvale, Calif.
The information requested by a client from an origin server generally includes a number of objects. For example, if a client requests an HTML web page, that page is an object. The page may also include one or more images (e.g., .jpg, .gif, or .tiff), advertisements, and other entities, which are also objects. When a user of a client machine initiates an HTTP request for a web page, if the page includes other objects, the client device typically automatically issues an additional request for each of those objects. Although these additional requests are transparent to the user, this process takes time, which adds to the overall network latency perceived by the user. In a network cache it is desirable to reduce such latency.
Certain network cache implementations attempt to reduce latency by minimizing the number of disk input/output operations (I/Os) required per object by, for example, storing certain critical information about the objects in main memory. One implementation of a network cache maintain a hash table that stores references to all objects that it has cached. Objects are accessed using meta-information contained in inodes, which are stored in a separate file. For a particular cached web page, each hash table entry stores a reference to each object included in the web page as well as a reference to the web page itself. As long as the inode file is resident in memory, sufficient meta-information exists such that an object can be accessed using a single disk I/O. Once the object has been read into memory, subsequent requests for the same object can be served from memory.
In reality, however, such perfect conditions are rarely achieved. The inode file tends to be so large that it generally is not possible to retain it completely in memory (i.e., some of it must be stored on disk), and subsequent requests are rarely served from memory. Often the number of disk I/Os per object is greater than one.
Also, references to related objects (e.g., objects from a particular web page) tend to get spread out randomly throughout the hash table. Consequently, to deliver a single web page that includes multiple objects to a client, the network cache may have to perform multiple, essentially random disk I/Os. The result is less than optimal throughput in serving client requests.